class Solution(object):
    def maximumOr(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        n = len(nums)
        # 预处理每个位置左侧的或运算前缀数组
        prefix = [0] * n
        prefix[0] = nums[0]
        for i in range(1, n):
            prefix[i] = prefix[i-1] | nums[i]  # prefix[i]表示nums[0]~nums[i]的或
        # 预处理每个位置右侧的或运算后缀数组
        suffix = [0] * n
        suffix[-1] = nums[-1]
        for i in range(n-2, -1, -1):
            suffix[i] = suffix[i+1] | nums[i]  # suffix[i]表示nums[i]~nums[n-1]的或
        res = 0  # 记录最大结果
        for i in range(n):
            # 计算左侧所有元素的或（不包括当前i）
            left = prefix[i-1] if i > 0 else 0
            # 计算右侧所有元素的或（不包括当前i）
            right = suffix[i+1] if i < n-1 else 0
            # 将当前元素左移k位后，与左右两侧的或一起做或运算
            cur = left | (nums[i] << k) | right
            # 更新最大值
            res = max(res, cur)
        return res 